# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 11:31:57 2020

@author: Administrator
"""

'''

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:

Input: nums = [1]
Output: 1
Example 3:

Input: nums = [0]
Output: 0
Example 4:

Input: nums = [-1]
Output: -1
Example 5:

Input: nums = [-2147483647]
Output: -2147483647
 

Constraints:

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
'''


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        '''
        20200917--李运辰
        没理解题目
        
        '''
        
        '''
        [-2,1,-3,4,-1,2,1,-5,4]

        max=-2

        i=1
        [-2,1,-3,4,-1,2,1,-5,4]
        max=1


        i=2
        [-2,1,-2,4,-1,2,1,-5,4]
        max=1

        i=3
        [-2,1,-2,4,-1,2,1,-5,4]
        max=4

        i=4
        [-2,1,-2,4,3,2,1,-5,4]
        max=4

        i=5
        [-2,1,-2,4,3,5,1,-5,4]
        max=5

        i=6
        [-2,1,-2,4,3,5,6,-5,4]
        max=6

        i=7
        [-2,1,-2,4,3,5,6,1,4]
        max=6

        i=8
        [-2,1,-2,4,3,5,6,1,5]
        max=6
        '''
        
        maxs =nums[0]
        n = len(nums)
        for i in range(1,n):
            nums[i] = max(nums[i]+nums[i-1],nums[i])
            
            if nums[i]>maxs:
                maxs =nums[i]
            
        return maxs
        
        
        
        
        